/*
 * @lc app=leetcode.cn id=390 lang=cpp
 *
 * [390] 消除游戏
 */

// @lc code=start
class Solution
{
public:
    int lastRemaining(int n)
    {
        int ans = 1;
        int k = 0;
        int step = 1;
        int count = n;

        while (count > 1)
        {
            if (k % 2 == 0)
            {
                ans += step;
            }
            else
            {
                ans = (count % 2 == 0) ? ans : ans + step;
            }
            k++;
            step *= 2;
            count /= 2;
        }

        return ans;
    }
};
// @lc code=end
